package gold.digger;

import gold.vo.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC655 {
    public long startExecuteTime = System.currentTimeMillis();

    class Solution {
        public List<List<String>> printTree(TreeNode root) {
            int height = getHigh(root);//求树的高度
            List<List<String>> ans = new ArrayList<>(height);
            int width = (int) Math.pow(2, height) - 1;//每层列表的长度
            List<String> ans_lev = new ArrayList<>();
            for (int i = 0; i < width; i++) ans_lev.add("");
            DFS(root, ans, ans_lev, 1, 0, width - 1);//层次遍历填充结果
            return ans;
        }

        private void DFS(TreeNode root, List<List<String>> ans, List<String> ans_lev, int depth, int lo, int hi) {
            if (root == null) return;//深度优先的层次遍历：获取节点准确位置
            if (ans.size() < depth) ans.add(new ArrayList<String>(ans_lev));
            int index = (lo + hi) / 2;//应该设置的位置
            ans.get(depth - 1).set(index, Integer.toString(root.val));
            DFS(root.left, ans, ans_lev, depth + 1, lo, index - 1);
            DFS(root.right, ans, ans_lev, depth + 1, index + 1, hi);
        }

        private int getHigh(TreeNode root) {//求树高
            if (root == null) return 0;
            return 1 + Math.max(getHigh(root.left), getHigh(root.right));
        }
    }

    public void run() {
        Solution solution = new Solution();
        List<Integer> list = new ArrayList<>();
        System.out.println(solution.toString());
    }

    public static void main(String[] args) throws Exception {
        LC655 an = new LC655();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
